// https://leetcode.cn/problems/maximal-square/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 使用动态规划计算最大正方形边长
// 2. 利用一维数组进行空间优化，记录左上、正上、左前的状态
// 3. 当前位置为'1'时，取三个方向最小值加一更新边长
// 4. 维护prev变量保存左上角状态，实现O(1)空间复杂度
// 5. 时间复杂度：O(M×N)，空间复杂度：O(N)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int maximalSquare(vector<vector<char>>& matrix) 
    {
        int m = matrix.size(), n = matrix[0].size();
        
        int ret = 0;
        vector<int> dp(n + 1, 0);
        for (int i = 1 ; i <= m ; i++)
        {
            int prev = 0;
            for (int j = 1 ; j <= n ; j++)
            {
                if (matrix[i - 1][j - 1] == '1')
                {
                    int temp = dp[j];
                    dp[j] = min({prev, dp[j], dp[j - 1]}) + 1;
                    prev = temp;
                    ret = max(ret, dp[j]);
                }
                else
                {
                    dp[j] = 0;
                    prev = 0;
                }
            }
        }

        return ret * ret;
    }
};

int main()
{
    vector<vector<char>> matrix1 = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
    vector<vector<char>> matrix2 = {{'0','1'},{'1','0'}};

    Solution sol;

    cout << sol.maximalSquare(matrix1) << endl;
    cout << sol.maximalSquare(matrix2) << endl;

    return 0;
}